package date_202403

//215. 数组中的第K个最大元素
//中等
//相关标签
//相关企业
//给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
//
//请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
//
//你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
//
//
//
//示例 1:
//
//输入: [3,2,1,5,6,4], k = 2
//输出: 5
//示例 2:
//
//输入: [3,2,3,1,2,4,5,5,6], k = 4
//输出: 4
//
//
//提示：
//
//1 <= k <= nums.length <= 105
//-104 <= nums[i] <= 104

func findKthLargest(nums []int, k int) int {
	if k > len(nums) {
		return -1
	}
	beginIdx := 0
	endIdx := len(nums) - 1
	for beginIdx < endIdx {
		curSortIdx := quickSortOnce(beginIdx, endIdx, nums)
		if curSortIdx == len(nums)-k {
			return nums[curSortIdx]
		} else if curSortIdx < len(nums)-k {
			beginIdx = curSortIdx + 1
		} else {
			endIdx = curSortIdx - 1
		}
	}

	return nums[len(nums)-k]
}

func quickSortOnce(begin int, end int, nums []int) int {
	if begin >= end {
		return begin
	}
	baseNum := nums[begin]
	leftIdx := begin
	rightIdx := end
	for leftIdx < rightIdx {
		for nums[rightIdx] >= baseNum && leftIdx < rightIdx {
			rightIdx--
		}
		if leftIdx < rightIdx {
			nums[leftIdx] = nums[rightIdx]
			leftIdx++
		}
		for nums[leftIdx] <= baseNum && leftIdx < rightIdx {
			leftIdx++
		}
		if leftIdx < rightIdx {
			nums[rightIdx] = nums[leftIdx]
		}
	}
	nums[leftIdx] = baseNum
	return leftIdx
}
